package basis.netease.hard;

import java.util.Scanner;

/**
 * 7-2 按公因数计算最大组件大小
 * 给定一个由不同正整数组成的非空数组 nums，考虑下面的构图：
 * 有 nums.length 个节点，按照从 nums[0]到 nums[nums.length-1]标记；
 * 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j] 之间才有一条边。
 * 返回构图中最大连通组件的大小。
 * 输入格式:
 * 输入为数组元素，空格分隔
 * 输出格式:
 * 输出最大连通组件的大小
 * 输入样例1:
 * 在这里给出一组输入。例如：
 * 4 6 15 35
 * 输出样例1:
 * 在这里给出相应的输出。例如：
 * 4
 * 输入样例2:
 * 在这里给出一组输入。例如：
 * 20 50 9 63
 * 输出样例2:
 * 在这里给出相应的输出。例如：
 * 2
 * 输入样例3:
 * 在这里给出一组输入。例如：
 * 2 3 6 7 4 12 21 39
 * 输出样例3:
 * 在这里给出相应的输出。例如：
 * 8
 * 注意：
 * 1 <= nums.length <= 2*10^4
 * 1 <= nums[i] <= 10^5
 * nums 中所有值都不同
 */
public class Main_2 {

    public static boolean hasCommonFactor(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a > 1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int[] nums = new int[input.length];
        int[] parent = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nums[i] = Integer.parseInt(input[i]);
            parent[i] = i;
        }
        for (int i = 0; i < parent.length; i++) {
            for (int j = i + 1; j < parent.length; j++) {
                if (hasCommonFactor(nums[i], nums[j])) {
                    union(parent, i, j);
                }
            }
        }
        int[] counts = new int[nums.length];
        int max = 0;
        for (int i = 0; i < parent.length; i++) {
            int root = find(parent, i);
            counts[root] += 1;
            max = Math.max(max, counts[root]);
        }
        System.out.println(max);
    }

    public static void union(int[] parent, int i, int j) {
        int rooti = find(parent, i);
        int rootj = find(parent, j);
        if (rooti != rootj) {
            parent[rooti] = rootj;
        }
    }

    public static int find(int[] parent, int i) {
        if (i != parent[i]) {
            parent[i] = find(parent, parent[i]);
        }
        return parent[i];
    }

}
